package com.itheima.algorithm.sort;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

// 双边快排
public class QuickSortHoare {
    public static void sort(int[] a) {
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a, left, right);
        quick(a, left, p - 1);
        quick(a, p + 1, right);
    }

    private static int partition(int[] a,int left,int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        // [0~9] right-left+1=3 [0,2]+4=[4,6]
        swap(a, idx, left);
        int pv = a[left]; // 基准点
        int i = left;
        int j= right;
        while (i < j) {
            // j从右往左找比基准点小(等于)的
            while(i<j && a[j]>pv) {
                j--;
            }
            // i从左往右找比基准点大的
            while(i<j && a[i]<= pv){
                i++;
            }
            // 交换位置
            swap(a,i,j);
        }
        swap(a,left,i);
        return i;
    }

    private static void swap(int [] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void main(String[] args) {
        int[] a = {9, 3, 7, 2, 8, 5, 1, 4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
